package com.lry.basic.algorithm.stack;

import java.util.Arrays;
import java.util.Stack;

public class SumSubarrayMins {


    public static void main(String[] args) {
        SumSubarrayMins sumSubarrayMins = new SumSubarrayMins();
        System.out.println(sumSubarrayMins.sumSubarrayMins(new int[]{1,3,1,2}));
    }

    public int sumSubarrayMins(int[] arr) {
        int[] left = new int[arr.length];//记录左边第一个<他的元素的下标
        int[] right = new int[arr.length];//记录右边第一个<=他的元素的下标

        Arrays.fill(right,arr.length);

        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<arr.length;i++){
            //维护递增栈
            while(!stack.isEmpty()&&arr[stack.peek()]>=arr[i]){
                Integer index = stack.pop();
                right[index] = i;
            }
            left[i] = stack.isEmpty()?-1:stack.peek();
            stack.push(i);
        }

        long mod = 1000000007;
        long ans = 0;
        for(int i=0;i<arr.length;i++){
            ans += (long)arr[i] *(i-left[i])*(right[i]-i)%mod;
            ans %=mod;
        }
        return (int)(ans);
    }

}
